//
// Created by edward on 22-11-17.
// 使用线性筛单机求解1e8以内的所有素数
// 输出执行时间 素数总数 素数总和
//      从小到大输出最大的10个素数
//

#include "utils.h"
#include <vector>
#include <fstream>
#include <cstring>

using namespace std;

using ll = long long;
constexpr int kMax = 1e8;
int prime[kMax], check[kMax];
//array<int, kMax> prime, check;
//vector<int> check(kMax, 0);
//vector<int> prime(kMax);
ll sum = 0, t;
int cnt = 0;

void output(edward::Timer& timer, const string& path) {
    ofstream os(path);
    //输出
    edward::print2file(os, "execution time:", timer.count(), "s");
    edward::print2file(os, "total number of primes found:", cnt);
    edward::print2file(os, "sum of all primes found:", sum);
    for (int i = cnt - 10, idx = 1; i < cnt; ++i, ++idx) {
        edward::print2file(os, idx, ":", prime[i]);
    }
}

void liner_prime() {
    edward::Timer timer;    //开始计时

    memset(check, 0, sizeof(check));

    //线性筛算法
    for (int i = 2; i < kMax; ++i) {
        if (!check[i]) {
            prime[cnt++] = i;
            sum += i;
        }
        for (int j = 0; j < cnt && (t = static_cast<ll>(i) * prime[j]) < kMax; ++j) {
            check[t] = true;
            if (i % prime[j] == 0) break;
        }
    }

    timer("time:");
    output(timer, "primes_number_v0.txt");
}

int main() {

    liner_prime();

    return 0;
}